package ca.etsmtl.log320;

import java.util.Arrays;

/**
 * Idées et concepts pour l'optimisation inspirée de: 
 * http://www.siteduzero.com/informatique/tutoriels/le-backtracking-par-l-exemple-resoudre-un-sudoku/pour-aller-plus-loin-34
 * et de:
 * http://www.byteauthor.com/2010/08/sudoku-solver/
 */

public class Optimised {

	//constantes
	int[] mBlocs = new int[] 
		   {0,0,0,
			3,3,3,
			6,6,6};
	int[] mMasks = new int[] { 0, 1,
			1 << 1, 
			1 << 2, 
			1 << 3, 
			1 << 4, 
			1 << 5, 
			1 << 6, 
			1 << 7, 
			1 << 8 };

	protected static final int ID_X = 0;
	protected static final int ID_Y = 1;
	protected static final int ID_POSS = 2;
	
	
	//grille de résultat	
	int[][] mGrille;

	//liste de l'ordre des cases à vérifier
	int[][] mList = new int[81][9];
	int mSize = 0;
	
	//cases déjà placées
	int[] notAllowedRow;
	int[] notAllowedCol;
	int[] notAllowedBloc;
	
	int[][] nNumberUsed;
	
	protected static final int ID_USED_NUMBER = 0;
	protected static final int ID_USED_FREQ = 1;
	
	
	public Optimised() {
	}
	
	public boolean calculateAnswer(int[][] resultat){
		notAllowedRow = new int[9];
		notAllowedCol = new int[9];
		notAllowedBloc = new int[9];
		nNumberUsed = new int[9][2];
		mGrille = resultat;

	    for (int n=0; n<9; n++) {
        	nNumberUsed[n][ID_USED_NUMBER]=(n+1);
	    }
	    // Enregistre dans les tableaux toutes les valeurs d�j� pr�sentes
	    int n;
	    for (int x=0; x < 9; x++) {
	        for (int y=0; y < 9; y++) {
	            if ( (n = resultat[x][y]) != 0) {
	            	notAllowedRow[x] |= (mMasks[n]);
	            	notAllowedCol[y] |= (mMasks[n]);
	            	notAllowedBloc[mBlocs[x]+(y/3)] |= (mMasks[n]);
	            	nNumberUsed[n-1][ID_USED_FREQ]++;
	            }
	        }
	    }
	   
	    createSortedList();
	    
	    return estValide(0);
	}

	
	// Calcule le nombre de valeurs possibles pour une case vide
	int getPossibilites(int x, int y) {
	    int poss = 0;
	    for (int n=1; n <= 9; n++) {
	        if ((notAllowedRow[x] & (mMasks[n])) == 0 
	        &&  (notAllowedCol[y] & (mMasks[n])) == 0 
	        &&  (notAllowedBloc[mBlocs[x]+(y/3)] & (mMasks[n])) == 0) {
	        	 poss++;
	        }
	    }
	    return poss;
	}
	
	 
	private void createSortedList() {
		//mList.clear();
		
		// cr�e et remplit une liste pour les cases vides � visiter
		int idx = 0;
	    for (int i=0; i < 9; i++) {
	        for (int j=0; j < 9; j++) {
	            if ( mGrille[i][j] == 0 ) {
	                mList[idx][ID_X] = i;
	                mList[idx][ID_Y] = j;
	                mList[idx][ID_POSS] = getPossibilites(i, j);
	                idx++;
	            }
	        }
	    }
	    
	    mSize = idx;
	    for (int i=idx; i <81; i++) {
            mList[i][ID_POSS] = 13;//more than 9, to be sorted at the end
	    }
	    	

	    java.util.Arrays.sort(nNumberUsed, new java.util.Comparator<int[]>() {
	        public int compare(int[] a, int[] b) {
	        	return b[ID_USED_FREQ] - a[ID_USED_FREQ];
	        }
	    });
	    
	    java.util.Arrays.sort(mList, new java.util.Comparator<int[]>() {
	        public int compare(int[] a, int[] b) {
	        	return a[ID_POSS] - b[ID_POSS];
	        }
	    });
	}
	
	
	boolean estValide(int idx)
	{
	    if(mSize <= idx)
	        return true;

		int[] c = mList[idx];
	 	
	    for (int i=0; i < 9; i++)
	    {
	    	/*if(nNumberUsed[i][ID_USED_FREQ] == 9)
	    		continue;*/
	    	int n = nNumberUsed[i][ID_USED_NUMBER];
	        // V�rifie dans les tableaux si la valeur est d�j� pr�sente
	        if ( (notAllowedRow[c[ID_X]] & (mMasks[n])) == 0 && (notAllowedCol[c[ID_Y]] & (mMasks[n])) == 0 && (notAllowedBloc[mBlocs[c[ID_X]]+(c[ID_Y]/3)] & (mMasks[n])) == 0)
	        {
	            // Ajoute n aux valeurs enregistr�es
            	notAllowedRow[c[ID_X]] |= (mMasks[n]);
            	notAllowedCol[c[ID_Y]] |= (mMasks[n]);
            	notAllowedBloc[mBlocs[c[ID_X]]+(c[ID_Y]/3)] |= (mMasks[n]);
            	//nNumberUsed[n-1][ID_USED_FREQ]++;
	            
		    	if(estValide(idx + 1)) {
	                // Ecrit le choix valide dans la grille
		    		mGrille[c[ID_X]][c[ID_Y]] = n;
	                return true;
	            }
	            // Supprime n des valeurs enregistr�es
            	notAllowedRow[c[ID_X]] &= (~(mMasks[n]));
            	notAllowedCol[c[ID_Y]] &= (~(mMasks[n]));
            	notAllowedBloc[mBlocs[c[ID_X]]+(c[ID_Y]/3)] &= (~(mMasks[n]));
            	//nNumberUsed[n-1][ID_USED_FREQ]--;
	        }
	    }
	 
	    return false;
	}

}

